#include "stdio.h"
#include "conio.h"
#define SIZEA 4
#define SIZEB 4


typedef struct node
{
    int Row;
    int Col;
    int Value;

    struct node *Next;
}Node,*List;


void InitList(List *p)
{
  List q;
  q =(List)malloc(sizeof(struct node));
  q->Next=NULL;
  *p = q;
  return;
}
void PrintList(List head)
{
    List forward;
    int i=1;
    forward=head->Next;
    while(forward!=NULL)
    {
        printf("%d:%d->%d        ",forward->Row,forward->Col,forward->Value);
        forward=forward->Next;
        if(i%5==0)
            printf("\n") ;
        i++;
    }
    printf("\n");
}

void  PrintMatrix(List head, int size)
{
    List forward;
    int i =0;
    forward=head->Next;
    while(i<size*size)
    {
        if(forward->Row==i/size+1&&forward->Col==i%size+1)
        {

            printf("%d ",forward->Value);

            forward=forward->Next;
        }
        else
        {
            printf("0 ");
        }
        i++;
        if(i%4==0)
            printf("\n");

    }
    printf("\n");
    return;
}
void InsertList(List head,int len,int value, int row,int col)
{
    int i=1;
    List back,forward;
    forward=head;
    back=head;
    forward=head->Next;
    while(i<=len)
    {
        if(forward==NULL)
        {
            forward=(List)malloc(sizeof(struct node));
            forward->Row=row;
            forward->Col=col;
            forward->Value=value;
            /*printf("*********new\n");   */

            back->Next=forward;
            back=forward;
            back->Next=NULL;
            return;
        }
        else if(forward->Row==row)    /*addition*/
        {
             if(forward->Col==col)
             {
                forward->Value=forward->Value+value;

            /* printf("*********add\n");  */
                return;
             }
             else if(forward->Col>col&&(back->Row<row||(back->Col<row&&back->Row==row)))
             {
                forward=(List)malloc(sizeof(struct node));
                forward->Row=row;
                forward->Col=col;
                forward->Value=value;

                forward->Next=back->Next;
                back->Next=forward;
                return;
             }



        }
        else if(forward->Row>row&&(back->Row<row||(back->Col<row&&back->Row==row)))
        {
              forward=(List)malloc(sizeof(struct node));
              forward->Row=row;
              forward->Col=col;
              forward->Value=value;

              forward->Next=back->Next;
              back->Next=forward;
              return;

        }

        back=forward;
        forward=forward->Next;
        i++;
    }
}
void Addition(List head1,List head2,List head3)
{
    int i=1;
    List forward1,forward2,forward3;
    forward1=head1->Next;
    forward2=head2->Next;

    while(forward1!=NULL)
    {
        /*printf("*%d-%d-%d\n",forward1->Row,forward1->Col,forward1->Value);*/
        InsertList(head3,i,forward1->Value,forward1->Row,forward1->Col);
        forward1=forward1->Next;
        i++;

    }

    while(forward2!=NULL)
    {
            /*printf("*%d-%d-%d\n",forward2->Row,forward2->Col,forward2->Value); */
        InsertList(head3,i,forward2->Value,forward2->Row,forward2->Col);
        forward2=forward2->Next;
        i++;
    }
   return;
}
void Mul(List head1,List head2,List head4)
{
    int i;
    List forward1,forward2;
    forward1=head1->Next;
    forward2=head2->Next;
    while(forward1)
    {

        while(forward2)
        {
           /* printf("++%d%d++\n",forward1->Col,forward2->Row);  */
            if(forward1->Col==forward2->Row)
            {
                InsertList(head4,i,forward1->Value*forward2->Value,forward1->Row,forward2->Col);  
                i++;
             }
            forward2=forward2->Next; 


        }
        forward2=head2->Next;
        forward1=forward1->Next;
        i++;
    }
    return;
}
void main()
{
    int row, col,i;                     /*even index store the position while the odd index store the vlaue */
    List matrix1, matrix2, matrix3, matrix4;
    int m1[]={11,1,14,1,22,1,41,1};   /*even index store the position while the odd index store the vlaue */
    int m2[]={11,1,21,1,31,1,41,1};
    InitList(&matrix1);
    InitList(&matrix2);
    InitList(&matrix3);
    InitList(&matrix4);
    for(i=1;i<=SIZEA*2;i+=2)  /*Insert the value to the matrix*/
        InsertList(matrix1,i, m1[i], m1[i-1]/10,m1[i-1]%10);
    for(i=1;i<=SIZEB*2;i+=2)
        InsertList(matrix2, i,m2[i], m2[i-1]/10,m2[i-1]%10);


    PrintList(matrix1);
    PrintList(matrix2);
    PrintMatrix(matrix1,4);
    PrintMatrix(matrix2,4);
    Addition(matrix1,matrix2,matrix3);
    Mul(matrix1,matrix2,matrix4);
    PrintMatrix(matrix3,4);
    PrintMatrix(matrix4,4);

    PrintList(matrix3);
    PrintList(matrix4);

    getch();
    return;
}
